graph.cpp

Go to the documentation of this file.
00001 /* graph.cpp */
00002 
00003 
00004 #include <stdio.h>
00005 #include <stdlib.h>
00006 #include <string.h>
00007 #include "graph.h"
00008 #include "instances.inc"
00009 
00010 
00011 template <typename captype, typename tcaptype, typename flowtype> 
00012         Graph<captype, tcaptype, flowtype>::Graph(int node_num_max, int edge_num_max, void (*err_function)(char *))
00013         : node_num(0),
00014           nodeptr_block(NULL),
00015           error_function(err_function)
00016 {
00017         if (node_num_max < 16) node_num_max = 16;
00018         if (edge_num_max < 16) edge_num_max = 16;
00019 
00020         nodes = (node*) malloc(node_num_max*sizeof(node));
00021         arcs = (arc*) malloc(2*edge_num_max*sizeof(arc));
00022         if (!nodes || !arcs) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }
00023 
00024         node_last = nodes;
00025         node_max = nodes + node_num_max;
00026         arc_last = arcs;
00027         arc_max = arcs + 2*edge_num_max;
00028 
00029         maxflow_iteration = 0;
00030         flow = 0;
00031 }
00032 
00033 template <typename captype, typename tcaptype, typename flowtype> 
00034         Graph<captype,tcaptype,flowtype>::~Graph()
00035 {
00036         if (nodeptr_block) 
00037         { 
00038                 delete nodeptr_block; 
00039                 nodeptr_block = NULL; 
00040         }
00041         free(nodes);
00042         free(arcs);
00043 }
00044 
00045 template <typename captype, typename tcaptype, typename flowtype> 
00046         void Graph<captype,tcaptype,flowtype>::reset()
00047 {
00048         node_last = nodes;
00049         arc_last = arcs;
00050         node_num = 0;
00051 
00052         if (nodeptr_block) 
00053         { 
00054                 delete nodeptr_block; 
00055                 nodeptr_block = NULL; 
00056         }
00057 
00058         maxflow_iteration = 0;
00059         flow = 0;
00060 }
00061 
00062 template <typename captype, typename tcaptype, typename flowtype> 
00063         void Graph<captype,tcaptype,flowtype>::reallocate_nodes(int num)
00064 {
00065         int node_num_max = (int)(node_max - nodes);
00066         node* nodes_old = nodes;
00067 
00068         node_num_max += node_num_max / 2;
00069         if (node_num_max < node_num + num) node_num_max = node_num + num;
00070         nodes = (node*) realloc(nodes_old, node_num_max*sizeof(node));
00071         if (!nodes) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }
00072 
00073         node_last = nodes + node_num;
00074         node_max = nodes + node_num_max;
00075 
00076         if (nodes != nodes_old)
00077         {
00078                 arc* a;
00079                 for (a=arcs; a<arc_last; a++)
00080                 {
00081                         a->head = (node*) ((char*)a->head + (((char*) nodes) - ((char*) nodes_old)));
00082                 }
00083         }
00084 }
00085 
00086 template <typename captype, typename tcaptype, typename flowtype> 
00087         void Graph<captype,tcaptype,flowtype>::reallocate_arcs()
00088 {
00089         int arc_num_max = (int)(arc_max - arcs);
00090         int arc_num = (int)(arc_last - arcs);
00091         arc* arcs_old = arcs;
00092 
00093         arc_num_max += arc_num_max / 2; if (arc_num_max & 1) arc_num_max ++;
00094         arcs = (arc*) realloc(arcs_old, arc_num_max*sizeof(arc));
00095         if (!arcs) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }
00096 
00097         arc_last = arcs + arc_num;
00098         arc_max = arcs + arc_num_max;
00099 
00100         if (arcs != arcs_old)
00101         {
00102                 node* i;
00103                 arc* a;
00104                 for (i=nodes; i<node_last; i++)
00105                 {
00106                         if (i->first) i->first = (arc*) ((char*)i->first + (((char*) arcs) - ((char*) arcs_old)));
00107                 }
00108                 for (a=arcs; a<arc_last; a++)
00109                 {
00110                         if (a->next) a->next = (arc*) ((char*)a->next + (((char*) arcs) - ((char*) arcs_old)));
00111                         a->sister = (arc*) ((char*)a->sister + (((char*) arcs) - ((char*) arcs_old)));
00112                 }
00113         }
00114 }

Generated on Sun Oct 26 18:22:20 2008 for maxflow-v3.0 by  doxygen 1.4.7